package previous.Test_0210;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //全排列3
    //总
    List<List<Integer>> ret1;
    //每个
    List<Integer> path1;
    //检查
    boolean[] check;
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret1=new ArrayList<>();
        path1=new ArrayList<>();
        check=new boolean[nums.length];
        Arrays.sort(nums);
        dfs1(nums,0);

        return ret1;
    }
    public void dfs1(int[] nums,int pos){
        //如果path长度与num相同，放入ret
        if(path1.size()==nums.length){
            ret1.add(new ArrayList<>(path1));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //合法
            //如果未被使用
            if(check[i]==false && (i==0 || nums[i]!=nums[i-1] || check[i-1]==true)){
                //选
                path1.add(nums[i]);
                //已使用，check==true
                check[i]=true;
                dfs1(nums,pos+1);
                //剪枝：重复
                check[i]=false;
                //回溯
                path1.remove(path1.size()-1);
            }
        }
    }
    //电话号码的字母组合
    String[] hash={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    //总的
    List<String> ret;
    //每条
    StringBuilder path;
    public List<String> letterCombinations(String digits) {
        ret=new ArrayList<>();
        path=new StringBuilder();
        if(digits.length()==0){
            return ret;
        }
        dfs(digits,0);
        return ret;
    }
    public void dfs(String digits,int pos){
        //递归出口
        if(digits.length()==pos){
            ret.add(path.toString());
            return;
        }
        char[] ch=hash[digits.charAt(pos)-'0'].toCharArray();
        for (int i = 0; i <ch.length ; i++) {
            path.append(ch[i]);
            dfs(digits,pos+1);
            //回溯
            path.deleteCharAt(path.length()-1);
        }
    }
    //括号生成
    List<String> ret2;
    StringBuilder path2;
    int left=0;
    int right=0;
    public List<String> generateParenthesis(int n) {
        ret2=new ArrayList<>();
        path2=new StringBuilder();
        dfs(n);
        return ret2;
    }
    public void dfs(int n){
        //递归出口
        if(right==n){
            ret2.add(path2.toString());
            return;
        }
        //合法
        if(left<n ){
            path2.append("(");
            left++;
            dfs(n);
            path2.deleteCharAt(path2.length()-1);
            left--;
        }
        if(left>right){
            path2.append(")");
            right++;
            dfs(n);
            path2.deleteCharAt(path2.length()-1);
            right--;
        }
    }
    //组合
    List<List<Integer>> ret3;
    List<Integer> path3;
    public List<List<Integer>> combine(int n, int k) {
        ret3=new ArrayList<>();
        path3=new ArrayList<>();
        dfs(n,k,1);
        return ret3;
    }
    public void dfs(int n,int k,int pos){
        if(path3.size()==k){
            ret3.add(new ArrayList<>(path3));
            return;
        }
        for (int i = pos; i <=n ; i++) {
            path3.add(i);
            dfs(n,k,i+1);
            path3.remove(path3.size()-1);
        }
    }

}
